#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
#include "queue"

using namespace std;

/*HJJ QQ479287006
 *给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]
示例 2：
输入：root = [1]
输出：[[1]]
示例 3：
输入：root = []
输出：[]
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
vector<vector<int>> levelOrderBottom(TreeNode *root) {
    vector<vector<int>> ret;
    vector<int> t;
    queue<TreeNode *> q;
    if (!root)
        return ret;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();

        for (int i = 0; i < size; ++i) {
            TreeNode *temp = q.front();
            t.push_back(temp->val);
            q.pop();
            if (temp->left)
                q.push(temp->left);

            if (temp->right)
                q.push(temp->right);
        }
        ret.push_back(t);
        t.clear();

    }

    reverse(ret.begin(), ret.end());
    return ret;
}